// https://leetcode.cn/problems/edit-distance/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 动态规划求解编辑距离问题（空间优化版）
// 2. 使用滚动数组将空间复杂度降至O(n)
// 3. 字符相同时：取三种操作的最小值（利用prev保存左上角状态）
// 4. 字符不同时：取三种操作的最小值+1
// 5. 时间复杂度：O(m×n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    int minDistance(string word1, string word2) 
    {
        int m = word1.size(), n = word2.size();

        word1 = " " + word1;
        word2 = " " + word2;

        vector<int> dp(n + 1, 0);
        for (int j = 1 ; j <= n ; j++)
        {
            dp[j] = j;
        }

        for (int i = 1 ; i <= m ; i++)
        {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1 ; j <= n ; j++)
            {
                int tmp = dp[j];
                if (word1[i] == word2[j])
                {
                    dp[j] = 1 + min({dp[j], dp[j - 1], prev - 1});
                }
                else
                {
                    dp[j] = 1 + min({dp[j], dp[j - 1], prev});
                }
                prev = tmp;
            }
        }

        return dp[n];
    }
};

int main()
{
    string word11 = "horse", word12 = "ros";
    string word21 = "intention", word22 = "execution";

    Solution sol;

    cout << sol.minDistance(word11, word12) << endl;
    cout << sol.minDistance(word21, word22) << endl;

    return 0;
}